#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <random>
#include <string>
#include <tuple>
#include <vector>

#include "BarkerPair.h"

#define INITIAL_POPULATION 1024

std::vector<int> generateRandomBinarySequence(int length) {
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<int> dist(0, 1);

    std::vector<int> sequence;
    sequence.reserve(length);

    for (int i = 0; i < length; ++i) {
        int num = dist(rng);
        sequence.push_back(num == 0 ? -1 : 1);
    }

    return sequence;
}

int getRandomNumber(int min, int max) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(min, max);
    return dis(gen);
}

float getRandomFloat() {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0.0, 1.0);
    return dis(gen);
}

std::tuple<int, int, double> init(int argc, char* argv[]) {
    int iterationCount = 100;
    int maximumPopulationSize = 100;
    double mutationRate = 0.4;

    if (argc > 1) {
        iterationCount = std::stoi(argv[1]);
    }
    if (argc > 2) {
        maximumPopulationSize = std::stoi(argv[2]);
    }
    if (argc > 3) {
        mutationRate = std::stod(argv[3]);
    }
    return std::make_tuple(iterationCount, maximumPopulationSize, mutationRate);
}

std::pair<int, int> countRunsAndMax(const std::vector<int>& nums) {
    if (nums.empty()) {
        return {0, 0};  // 如果 vector 为空，则游程数量和最大游程长度都为 0
    }

    int count = 1;       // 默认至少存在一个游程
    int maxRun = 1;      // 默认最大游程长度为 1
    int currentRun = 1;  // 当前游程的长度
    for (size_t i = 1; i < nums.size(); ++i) {
        // 如果当前元素与前一个元素相同，则增加当前游程的长度
        if (nums[i] == nums[i - 1]) {
            ++currentRun;
            maxRun = std::max(maxRun, currentRun);  // 更新最大游程长度
        } else {
            ++count;  // 遇到不同的元素，则认为是一个新的游程
            currentRun = 1;  // 重置当前游程的长度
        }
    }
    return {count, maxRun};
}

std::vector<BarkerPair> generate(int length) {
    std::vector<BarkerPair> generations;
    while (generations.size() < INITIAL_POPULATION) {
        BarkerPair bcp{generateRandomBinarySequence(length),
                       generateRandomBinarySequence(length)};

        // 游程个数集中在 [n/2, n]，且游程长度最大值小于等于 n/2
        auto [cnt1, maxRun1] = countRunsAndMax(bcp.x);
        auto [cnt2, maxRun2] = countRunsAndMax(bcp.y);
        if (cnt1 < (length / 2) || maxRun1 > (length / 2)) continue;
        if (cnt2 < (length / 2) || maxRun2 > (length / 2)) continue;

        generations.push_back(bcp);
    }
    return generations;
}

BarkerPair simulated_annealing(const BarkerPair& individual) {
    BarkerPair current = individual;
    BarkerPair best = individual;
    double initial_temperature = 100;
    double minimum_temperature = 1;
    double cooling_rate = 0.99;
    double current_temperature = initial_temperature;

    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(0, current.x.size() - 1);

    while (current_temperature > minimum_temperature) {
        BarkerPair new_solution = current;

        // 对个体的x和y进行随机扰动
        int index = distribution(generator);
        new_solution.x[index] = -new_solution.x[index];
        index = distribution(generator);
        new_solution.y[index] = -new_solution.y[index];

        double current_energy = current.peak;
        double new_energy = new_solution.peak;
        double energy_difference = new_energy - current_energy;

        if (energy_difference < 0 ||
            getRandomFloat() < exp(-energy_difference / current_temperature)) {
            current = new_solution;
        }

        if (current.peak > best.peak) {
            best = current;
        }

        current_temperature *= cooling_rate;
    }

    return best;
}

int main(int argc, char* argv[]) {
    std::cout << "=============================" << std::endl;

    auto [iterationCount, maximumPopulationSize, mutationRate] =
        init(argc, argv);

    int length = 0;
    std::cout << "please input length:" << std::endl;
    std::cin >> length;

    std::vector<BarkerPair> generations = generate(length);

    int currentGeneration = 1;
    do {
        std::sort(generations.begin(), generations.end());
        std::cout << generations[0] << std::endl;
        if (currentGeneration % iterationCount == 0) {
            std::ofstream outputFile("bcp-" + std::to_string(length) + "-" +
                                     std::to_string(currentGeneration) +
                                     ".txt");
            if (!outputFile.is_open()) {
                std::cerr << "Error opening the file." << std::endl;
                return -1;
            }

            for (int i = 0; i < generations.size(); ++i) {
                outputFile << generations[i] << "\n";
            }
            outputFile.close();
            std::cout << "saved generation: " << currentGeneration << std::endl;
        }

        std::vector<BarkerPair> nextGenerations;
        nextGenerations.reserve(maximumPopulationSize);

        // long all = 0;
        // for (int i = 0; i < generations.size(); ++i) {
        //     all += std::abs(generations[i].peak);
        // }

        // 选择算子
        for (int i = 0; i < 10; ++i) {
            nextGenerations.push_back(generations[i]);
        }

        for (int i = 10; i < generations.size(); ++i) {
            double p = generations[i].peak / length;
            double r = getRandomFloat();
            if (p >= r) {
                nextGenerations.push_back(generations[i]);
            }
        }

        // 交叉算子
        while (nextGenerations.size() < maximumPopulationSize) {
            // 锦标赛选择两个父代
            int idx1 = getRandomNumber(0, generations.size() - 1);
            int idx2 = getRandomNumber(0, generations.size() - 1);

            std::vector<int> x1 = generations[idx1].x;
            std::vector<int> y1 = generations[idx1].y;
            std::vector<int> x2 = generations[idx2].x;
            std::vector<int> y2 = generations[idx2].y;

            std::vector<int> mx{x1};
            std::vector<int> my{y1};
            std::vector<int> nx{x2};
            std::vector<int> ny{y2};
            idx1 = getRandomNumber(0, length - 1);
            for (int i = idx1; i < length; ++i) {
                mx[i] = x2[i];
                nx[i] = x1[i];
            }

            idx2 = getRandomNumber(0, length - 1);
            for (int i = idx2; i < length; ++i) {
                my[i] = y2[i];
                ny[i] = y1[i];
            }

            // 变异算子
            int tmpIdx = getRandomNumber(0, length - 1);
            if (getRandomFloat() < mutationRate) {
                mx[tmpIdx] = -mx[tmpIdx];
            }
            tmpIdx = getRandomNumber(0, length - 1);
            if (getRandomFloat() < mutationRate) {
                my[tmpIdx] = -my[tmpIdx];
            }
            tmpIdx = getRandomNumber(0, length - 1);
            if (getRandomFloat() < mutationRate) {
                nx[tmpIdx] = -nx[tmpIdx];
            }
            tmpIdx = getRandomNumber(0, length - 1);
            if (getRandomFloat() < mutationRate) {
                ny[tmpIdx] = -ny[tmpIdx];
            }
            
            BarkerPair child1{mx, my};
            BarkerPair child2{nx, ny};
            // 应用模拟退火优化
            child1 = simulated_annealing(child1);
            child2 = simulated_annealing(child2);

            nextGenerations.push_back(child1);
            nextGenerations.push_back(child2);
        }

        generations = std::move(nextGenerations);  // 使用移动语义提高效率
        currentGeneration++;
    } while (true);

    std::cout << std::endl << "=============================" << std::endl;
}
